#include <stdio.h>
#include <stdlib.h>
#include "mergesort.h"

void printArray1(int* a, int length)
{
    printf("call printArray\n");
    for (int i = 0; i < length; ++i)
    {
        printf("%d,", a[i]);
    }
    printf("\n");
}
void merge(int* a, int* temp ,int left, int center, int right) 
{
    int i = left;
    int j = center + 1;
    int k = 0;
    int length = right - left;
    while((i <= center) && (j <= right))
    {
        if (a[i] <= a[j])
        {
            temp[k++] = a[i++];
        }
        else
        {
            temp[k++] = a[j++]; 
        }
    }

    while(i <= center)
    {
        temp[k++] = a[i++];
    }

    while(j <= right)
    {
        temp[k++] = a[j++];
    }

    for (int i = 0; i <= length; ++i)
    {
        a[left+i] = temp[i];
    }

}
void mSort(int* a, int* temp, int start, int end)
{
    if((end - start) < 0)
    {
        printf("error\n");
        return;
    }
    if ((end - start) == 0)
    {
        return;
    }

    int center;
    center = (start + end)/2;
    mSort(a, temp, start, center);
    mSort(a, temp, center + 1, end);
    merge(a, temp, start, center, end);
}

void swap(int& a, int& b)
{
    int temp;
    temp = a;
    a = b;
    b = temp;   
}

int media3(int*a, int start, int end)
{
    int center;
    int choosex;
    int temp;

    center = (start + end)/2;
    choosex = center;
    
    printf("[media3]center %d\n", center);
    if(a[start] > a[choosex])
    {
        swap(a[start], a[choosex]);
    }

    if (a[end] < a[choosex])
    {
        swap(a[end], a[choosex]);
    }

    if(a[start] > a[choosex])
    {
        swap(a[start], a[choosex]);
    }

    swap(a[end], a[choosex]);
    printf("[media3]s[media3]tart %d %d choosex %d end choosex\n", start, a[start], a[end]);
    printf("[media3]\n");
    printArray1(a, end + 1);
    return a[end];



}
void qSort(int*a, int start, int end)
{
    printf("start %d end %d\n", start, end);
    if (end - start < 0)
    {
        printf("error\n");
        return;
    }

    if(end - start == 0)
    {
        printf("end is equal to start\n");
        return;
    }
        
    int choosex;
    int i = start - 1;
    int j = end;
    printf("before end\n");
    printArray1(a, end+1);
    choosex = media3(a, start, end);
    while(1)
    {
        while(a[++i] < choosex){
            printf("i print %d %d\n", i, j); 
        } 
        while(a[--j] > choosex)
        {   
            printf("j print;%d %d\n", i, j);
        } 
        if (i < j){
            printf("swap\n");
            printArray1(a, end+1);
            swap(a[i], a[j]);
        }
        else
            break;
        
    }
    printf("%d %d\n", i, j);
    printArray1(a, end+1);
    swap(a[i], a[end]);
    printArray1(a, end+1);
    printf("call another level\n\n");
    if (i - 1 >= start)
        qSort(a, start, i - 1);
    if (i + 1 <= end)
    {
        qSort(a, i + 1 , end);
    }
    

}